package tree;

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.*;


/**
 * @Author leecho
 * @Date: 2021/10/27 14:58
 * @Version 1.0
 */

public class HuffmanTreeCodeDemo {
    public static void main(String[] args) throws Exception {
//        String content = "i like like like java do you like a java";

        HuffManTreeCode huffManTreeCode = new HuffManTreeCode();

//        List<HuffManCodeNode> nodes = huffManTreeCode.getNode(content);
//
//        System.out.println(nodes);
//
//        HuffManCodeNode manCodeNode = huffManTreeCode.huffmanTree(nodes);
//
//        System.out.println("==============");
//
//        huffManTreeCode.getCodes(manCodeNode);

//        huffManTreeCode.huffmanCode(content);

//        byte[] zip = huffManTreeCode.zip(content);
//
//        for (byte b : zip) {
//            System.out.printf("%5d",b);
//        }
//
//        System.out.println("=============");
//
//        byte[] decode = huffManTreeCode.decode(huffmanMap, zip);
//
//        System.out.println(new String(decode));
//        System.out.println(huffManTreeCode.huffmanCode(content).toString());

        String filePath1 = "f://5.jpg";
        String outPath2 = "f://3.zip";

        String filePath = "f://3.zip";
        String outPath = "f://6.jpg";

//       huffManTreeCode.decodeFile(filePath1,outPath2);

        huffManTreeCode.unZipFile(filePath,outPath);
    }
}

/*
* 思路
* - 压缩
*   - 先创建一个赫夫曼二叉树
*     - 将传入的字符统计出每一个出现的次数
*         - 节点中数据域由data和weight属性，其中data代表字符，weight代表出现的次数
*   - 设置每一个叶子结点的赫夫曼编码
*     - 左边为"0" 右边为"1"
*   - 生成整个字符完整的赫夫曼编码
*     - 遍历传入的字符，一一对应拼接到一个字符串上
*   - 将生成的完整赫夫曼编码进行压缩
*     - 以8字节为一组，进行补码成十进制
* - 解压
*   - 得到数组和对应的赫夫曼编码表，将获得的压缩后的数组进行转化成二进制
*       - 得到的数组，进行反编码获得初始的赫夫曼完整编码
*           - 在数组最后的一个数字前进行补码截取后8位
*           - 数组的最后一个数字直接拼接到字符串上
*       - 根据传过来的赫夫曼编码表，新建一个解码表
*           - 传过来的赫夫曼编码表的key为新表的value，value为新表的key
*       - 根据新建的解码表解码得到的完整赫夫曼编码
*           - 从第一个字符开始扫描，截取完整编码
*               - 把截取到的字符串与新建的解码表对应，如果有则从下一个继续扫描
*               - 如果没有则增长扫描的字符串，直到有对应的为止
*       - 输出得到的数组
* */
class HuffManTreeCode {

    static Map<Byte, String> huffmanMap = new HashMap<Byte, String>();

    static StringBuilder stringBuilder = new StringBuilder();

    public void decodeFile(String filePath,String outPath) throws Exception{
        FileInputStream is = new FileInputStream(filePath);

        FileOutputStream os = new FileOutputStream(outPath);

        byte[] b = new byte[is.available()];

        is.read(b);

        byte[] bytes = huffmanZip(b);

        ObjectOutputStream oos = new ObjectOutputStream(os);

        oos.writeObject(bytes);

        oos.writeObject(huffmanMap);

        is.close();
        os.close();
        oos.close();
    }

    public void unZipFile(String filePath,String outPath) throws Exception{
        FileInputStream is = new FileInputStream(filePath);

        ObjectInputStream ois = new ObjectInputStream(is);

        byte[] bytes =(byte[]) ois.readObject();

        Map<Byte,String> huffmanCodes = (Map<Byte, String>) ois.readObject();

        byte[] decode = decode(huffmanCodes, bytes);

        FileOutputStream os = new FileOutputStream(outPath);

        os.write(decode);

        is.close();
        ois.close();
        os.close();
    }

    public byte[] huffmanZip(byte[] bytes){
        List<HuffManCodeNode> nodes = getNode(bytes);
        HuffManCodeNode node = huffmanTree(nodes);

        getCodes(node);
        StringBuilder stringBuilder = new StringBuilder();
        for (byte b : bytes) {
            stringBuilder.append(huffmanMap.get(b));
        }

        byte[] huffmanZip = zip(stringBuilder);

        return huffmanZip;
    }

    public String byteToBitString(boolean flag,byte b){
        int temp = b;

        if (flag){
            temp |= 256;
        }
        String str = Integer.toBinaryString(temp);
        if (flag){
            return str.substring(str.length() - 8);
        } else {
            return str;
        }
    }

    public byte[] decode(Map<Byte, String> huffmanMap,byte[] huffmanBytes){
        StringBuilder stringBuilder = new StringBuilder();

        for(int i = 0; i < huffmanBytes.length; i++) {
            byte b = huffmanBytes[i];
            boolean flag = (i == huffmanBytes.length - 1);
            stringBuilder.append(byteToBitString(!flag, b));
        }

        Map<String, Byte> byteHashMap = new HashMap<>();

        for (Map.Entry<Byte,String> entry: huffmanMap.entrySet()){
            byteHashMap.put(entry.getValue(),entry.getKey());
        }

        List<Byte> list = new ArrayList<>();

        for (int i = 0; i < stringBuilder.length(); ) {
            int count = 1;
            boolean flag = true;
            Byte b =null;

            while (flag){
                String s1 =stringBuilder.substring(i, i + count);
                b = byteHashMap.get(s1);
                if (b == null){
                    count++;
                } else {
                    flag = false;
                }
            }
            list.add(b);
            i += count;
        }

        byte[] b =new byte[list.size()];

        for (int i = 0; i < b.length; i++) {
            b[i] = list.get(i);
        }

        return b;
    }

    public void getCodes(HuffManCodeNode node) {
        this.getCodes(node, "", stringBuilder);
        System.out.println("生成的赫夫曼编码表为：");
        for (Map.Entry<Byte, String> entry : huffmanMap.entrySet()) {
            int c = entry.getKey();
            char s = (char) c;
            System.out.println(" 字符为：" + s + "  " + "编码为：" + entry.getValue());
        }
        System.out.println("<=================>");
    }

    public StringBuilder huffmanCode(String content) {
        byte[] bytes = content.getBytes();

        List<HuffManCodeNode> nodes = getNode(bytes);

        HuffManCodeNode node = huffmanTree(nodes);

        getCodes(node);
        StringBuilder stringBuilder = new StringBuilder();
        for (byte b : bytes) {
            stringBuilder.append(huffmanMap.get(b));
        }
        return stringBuilder;
    }

    public byte[] zip(String content){
        StringBuilder stringBuilder = huffmanCode(content);
        return this.zip(stringBuilder);
    }

    public byte[] zip(StringBuilder huffmancode){
        int len = (huffmancode.length()+7) / 8;

        byte[] by = new byte[len];
        int index = 0;
        for (int i = 0; i < huffmancode.length(); i+=8) {
            String s;

            if (i+8 > huffmancode.length()){
                s = huffmancode.substring(i,huffmancode.length());
            } else {
                s = huffmancode.substring(i, i + 8);
            }

            by[index] =(byte) Integer.parseInt(s,2);
            index++;
        }

        return by;
    }

    /*
    * 生成对应赫夫曼编码
    * */
    public void getCodes(HuffManCodeNode node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
        stringBuilder1.append(code);

        if (node != null) {
            if (node.data == null) {
                getCodes(node.left, "0", stringBuilder1);
                getCodes(node.right, "1", stringBuilder1);
            } else {
                huffmanMap.put(node.data, stringBuilder1.toString());
            }
        }
    }

    /*
     * 统计每一个符号出现的次数
     * */
    public List<HuffManCodeNode> getNode(byte[] bytes ) {
        ArrayList<HuffManCodeNode> codeNodes = new ArrayList<>();
        HashMap<Byte, Integer> counts = new HashMap<>();

        for (byte b : bytes) {
            counts.merge(b, 1, Integer::sum);
        }

        /*Integer count = counts.get(b);
         *if (count == null){
            counts.put(b,1);
          } else {
            counts.put(b,count+1);
          }*/

        for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
            codeNodes.add(new HuffManCodeNode(entry.getKey(), entry.getValue()));
        }

        return codeNodes;
    }

    /*
     * 生成一个赫夫曼树
     * */
    public HuffManCodeNode huffmanTree(List<HuffManCodeNode> nodes) {
        Collections.sort(nodes);
        while (nodes.size() > 1) {
            HuffManCodeNode leftNode = nodes.get(0);
            HuffManCodeNode rightNode = nodes.get(1);

            HuffManCodeNode parent = new HuffManCodeNode(null, leftNode.weight + rightNode.weight);

            parent.left = leftNode;
            parent.right = rightNode;

            nodes.remove(leftNode);
            nodes.remove(rightNode);

            nodes.add(parent);
            Collections.sort(nodes);
        }

        return nodes.get(0);
    }

}

class HuffManCodeNode implements Comparable<HuffManCodeNode> {
    Byte data;
    int weight;
    HuffManCodeNode left;
    HuffManCodeNode right;

    public HuffManCodeNode(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    public void infixList() {
        System.out.println(this.toString());
        if (this.left != null) {
            this.left.infixList();
        }
        if (this.right != null) {
            this.right.infixList();
        }
    }

    @Override
    public String toString() {
        return "HuffManCodeNode{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }

    @Override
    public int compareTo(HuffManCodeNode o) {
        return this.weight - o.weight;
    }
}